When quality of service (QoS) of packet-based communications is a concern, network infrastructure may be configured to implement scheduling policies to provide differentiated and managed service levels to the different types of network traffic. One such approach is to lump the different types of network communications into aggregate units of traffic called “classes”. This simplifies the packet scheduling problem because it allows all packets belonging to one class to be treated uniformly, even if they belong to different communication flows.
Link scheduling within a network device that implements this class-oriented approach to traffic management is often called “class-based queuing” or “class-based scheduling”. Examples of class-based scheduling algorithms include CBQ (Class Based Queuing), HFSC (Hierarchical Fair Service Curve), HPFQ (Hierarchical Packet Fair Queuing), HTB (Hierarchical Token Buckets), and CB-WFQ (Class Based-Weighted Fair Queuing).
In a class-based queuing system, individual packets may be assigned to different classes or levels of service. Each such class has associated parameters (e.g., priority, bandwidth) that affect how packets assigned to that class are treated for scheduling, transmission and/or other purposes. Typically, a QoS policy defines how packets are mapped to classes of services, and may include one or more classification rules that operate on the data and control information present in a network packet in order to select an appropriate class. The class may be explicitly configured into the packets, as with DiffServ (Differentiated Services), or the class may be determined by configurable classification rules as part of a QoS system implemented within the device.
As packets arrive at a network device over one or more incoming communication links and are to be sent over a particular outgoing communication link incident to that device, the rate at which packets arrive may exceed the rate at which the link can service the packets. In this case, the device typically places the packets in a queuing module related to that link, and a scheduling algorithm determines, from the set of available packets in the system, which packet should be sent each time the link becomes available to transmit another packet.
In the case of class-based queuing, the queue for the overall link is represented as a set of class queues, one for each class specified by the QoS policy or policies. Each time a packet can be transmitted, the scheduler determines which class should go next, dequeues a packet from the corresponding class queue, and transmits the dequeued packet on the network link. Each class queue is in turn managed by a suitable queue management policy, e.g., FIFO (First-In, First-Out) drop-tail, RED (Random Early Discard), flow-based weighted fair queuing, and so forth.
QoS policies are created to establish class parameters like bandwidth and priority, and are typically configured into a class-based scheduler according to operator input through a network management system or user interface.
Typically, QoS policies and classification rules are devised such that all of the packets that comprise a communication flow are identified with the same class. The term flow is used to generically refer to all of the packets that comprise a particular network conversation between two process end points. In the TCP/IP (Transport Control Protocol/Internet Protocol) architecture, a flow is uniquely identified by a tuple consisting of the IP source address, the IP destination address, the IP protocol type, the transport protocol source port, and the transport protocol destination port.
For example, a flow might correspond to a Web connection between a computer desktop at an office and a Web application server in a company's data center using TCP. Or, a flow might correspond to a voice over IP (VoIP) connection between two telephones coupled via a corporate intranet, wherein the VoIP packets are conveyed via Real-time Transport Protocol (RTP) over User Datagram Protocol (UDP).
All the packets of the web connection would typically be classified into one class, and all of the packets of the VoIP call would be likewise classified into another class. A flow in which all packets are assigned to the same class of service may be termed a “homogeneous communication flow”.
Homogenous communication flows interact well with class-based scheduling algorithms because schedulers that implement such algorithms generally operate to transmit packets from a class in the order they were received into that class. That is, class-based scheduling algorithms are generally order preserving in that the packets assigned to a given class are either: (1) serviced in FIFO order from within the class, or (2) serviced by a queue management algorithm where the ordering of packets comprising a flow is preserved even when the ordering of packets across flows might not be preserved (e.g., in weighted fair queuing). In either case, when a homogeneous communication flow traverses a class-based scheduler, all of the packets of the flow enter the same class due to the homogeneous nature of the flow, and thus are serviced on the output link in the same order they arrived at the input link.
However, it may be desirable to dynamically vary the class of service assigned to a given communication flow by assigning different classes to the various packets within the communication flow. This may be useful, for example, when different types of application messages are multiplexed onto a common communication flow. At one time the flow may carry interactive traffic, which requires a high class of service, while at another time the flow may carry a non-interactive print job, which can be adequately supported with a lower class of service. A flow for which the class of service varies across the packets comprising that flow may be termed a “heterogeneous communication flow”.
Computing environments in which heterogeneous communication flows may be found include those that employ the ICA (Independent Computing Architecture) protocol by Citrix Systems, Inc. or the Remote Desktop Protocol (RDP) developed by Microsoft Corporation. The ICA protocol allows communication traffic from multiple virtual channels to be interleaved in one TCP connection, such as between a client device and a server computer.
For example, the ICA protocol may be used to allow a client application to run in a centralized corporate data center while the user accesses the client from a thin-client terminal over a wide-area network. The ICA protocol utilizes different virtual channels that are interleaved on top of a common TCP connection, where the different channels may correspond to computer screen updates on the client, video serving, printer mapping, mouse movements, etc.
Contention can arise when one user is performing a non-interactive but data-intensive task like printing, while another user is performing an interactive but lightweight task like moving a mouse across the screen. In this case, it is undesirable for the print traffic in one user's flow to adversely impact the mouse movements in another user's flow because of queuing in the network.
Resolving and managing such contention is precisely the role of QoS. However, if traditional class-based queuing were utilized, wherein a common class would be assigned to all the packets of all the ICA connections (e.g., by using a classification rule that matched TCP packets whose TCP ports indicated the ICA protocol), there would be no way to distinguish between the various priorities of the various virtual channels among the various ICA connections.
Instead, a QoS rule could be configured to implement a policy that differentiates among the packets that carry messages from the different virtual channels. To facilitate this, ICA includes a priority field associated with each virtual channel. Thus, a QoS policy could be implemented that inspects the priority field of the virtual channel header indicated in the ICA message carried in a TCP segment as it appears in the network as an IP packet. Parsing packet headers and inspecting the application-level data carried in network packets in this fashion for various purposes is sometimes called “deep packet inspection” (DPI).
DPI can be used to classify the packets of an ICA connection with various message types resulting in a range of classes being assigned to the different packets comprising the connection, thus resulting in a heterogeneous communication flow. Unfortunately, a problem arises when such a flow traverses a class-based scheduler.
In particular, the ICA packets will be managed as different classes by the scheduler in accordance with the DPI policy. That is, some packets of the heterogeneous flow will be queued as one class while other packets of the heterogeneous flow can simultaneously be queued as another class. To provide service differentiation, the class-based scheduler will schedule packets from the various classes in non-FIFO order. At times, this will invariably cause higher-priority class packets to be scheduled ahead of lower-priority class packets from the same heterogeneous flow even if the lower-priority packets arrived first.
Consequently, some packets of a heterogeneous communication flow that are subjected to QoS scheduling are likely to be received out of order at their destination. This can be problematic when the communication flow corresponds to a transport protocol that preserves the delivery ordering of data, including the ubiquitous TCP.
In the case of TCP, when packets are received out of order, they are buffered by the protocol until the missing data arrives. Only until a contiguous, sequenced portion of data arrives at the receiving host can TCP deliver that data to the application. If higher priority packets arrive before lower priority packets (e.g., because of a QoS policy applied in the network), TCP must then wait until the lower priority packets arrive and deliver those before the higher priority packets can be delivered, in order to preserve in-order delivery of data. Thus, in this scenario, the QoS policy failed to enhance the performance of the protocol or application.
Moreover, communication throughput can actually be made worse as the destination device reorders the flow's packets and/or requests retransmission of packets it believes were lost. The higher classification assigned to some packets in the flow may therefore end up having no benefit, or may even have a detrimental effect on the entire flow.